/*
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
示例 2:

输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:

输入: [1,2,3,4,5,6,7,8,9]
输出: 2
进阶:
你能否用 O(n) 时间复杂度完成此题?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/wiggle-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/


//几条推论：（1）摇摆序列必定可以从首元素开始，从尾元素结束
//参考https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        /*
        int len=nums.size();
        if(len<2){
            return len;
        }
        if(len==2){
            return nums[0]==nums[1]?1:2;
        }
        int last=0;
        int cur=1;
        int num=2;
        int mode=false;// 小 大 小：true, 大 小 大： fasle
        if(nums[cur]==nums[last]){
            num=1;
        }
        for(int i=2;i<len;i++){
            
            //if(((nums[cur]-nums[last])<0&&(nums[i]-nums[cur])>0)||((nums[cur]-nums[last])>0&&(nums[i]-nums[cur])<0)||(nums[cur]==nums[last]&&nums[i]!=nums[cur])){
            //    num++;
            //    cout<<"last:"<<nums[last]<<",cur:"<<nums[cur]<<",next:"<<nums[i]<<endl;
            //} 
            
            if((nums[cur]-nums[last])<0&&(nums[i]-nums[cur])>0){
                num++;
                cout<<"last:"<<nums[last]<<",cur:"<<nums[cur]<<",next:"<<nums[i]<<endl;
            } 
            if((nums[cur]-nums[last])>0&&(nums[i]-nums[cur])<0){
                num++;
                cout<<"last:"<<nums[last]<<",cur:"<<nums[cur]<<",next:"<<nums[i]<<endl;
            }
            if(nums[cur]==nums[last]&&nums[i]!=nums[cur]){
                num++;
                cout<<"last:"<<nums[last]<<",cur:"<<nums[cur]<<",next:"<<nums[i]<<endl;
            }
            last=cur;
            cur=i;
        }
        return num;
        */
       int len=nums.size();
        if(len<2){
            return len;
        }
        int up=1;
        int down=1;
        for(int i=1;i<len;i++){
            if(nums[i]>nums[i-1]){
                up=down+1;
            }
            if(nums[i]<nums[i-1]){
                down=up+1;
            }
            //cout<<"up:"<<up<<",down:"<<down<<endl;
        }
        return max(up,down);

        //dp 
        /*
        if(nums.size()<2){
            return nums.size();
        }
        vector<int> down(nums.size(),0);
        vector<int> up(nums.size(),0);
        down[0]=1;
        up[0]=1;
        for(int i=1;i<nums.size();i++){
            if(nums[i]>nums[i-1]){
                up[i]=down[i-1]+1;
                down[i]=down[i-1];
            } else if(nums[i]<nums[i-1]){
                down[i]=up[i-1]+1;
                up[i]=up[i-1];
            } else{
                down[i]=down[i-1];
                up[i]=up[i-1];
            }
        } 
        return max(down[nums.size()-1],up[nums.size()-1]);
        */

       //贪心
        if(nums.size()<2){
            return nums.size();
        }
        
        int direction=nums[1]-nums[0];
        int count=(direction==0?1:2);
        int diff=0;
        for(int i=2;i<nums.size();i++){
            diff=nums[i]-nums[i-1];
            if((diff<0&&direction>=0)||(diff>0&&direction<=0)){
                direction=diff;
                count++;
            }
        }
        return count;
        
    }
};

int main(){
    Solution s;
    vector<int> in{372,492,288,399,81,2,320,94,416,469,427,117,265,357,399,456,496,337,355,219,475,295,457,350,490,470,281,127,131,36,430,412,442,174,128,253,1,56,306,295,340,73,253,130,259,223,14,79,409,384,209,151,317,441,156,275,140,224,128,250,290,191,161,472,477,125,470,230,321,5,311,23,27,248,138,284,215,356,320,194,434,136,221,273,450,440,28,179,36,386,482,203,24,8,391,21,500,484,135,348,292,396,145,443,406,61,212,480,455,78,309,318,84,474,209,225,177,356,227,263,181,476,478,151,494,395,23,114,395,429,450,247,245,150,354,230,100,172,454,155,189,33,290,187,443,123,59,358,241,141,39,196,491,381,157,157,134,431,295,20,123,118,207,199,317,188,267,335,315,308,115,321,56,52,253,492,97,374,398,272,74,206,109,172,471,55,452,452,329,367,372,252,99,62,122,287,320,325,307,481,316,378,87,97,457,21,312,249,354,286,196,43,170,500,265,253,19,480,438,113,473,247,257,33,395,456,246,310,469,408,112,385,53,449,117,122,210,286,149,20,364,372,71,26,155,292,16,72,384,160,79,241,346,230,15,427,96,95,59,151,325,490,223,131,81,294,18,70,171,339,14,40,463,421,355,123,408,357,202,235,390,344,198,98,361,434,174,216,197,274,231,85,494,57,136,258,134,441,477,456,318,155,138,461,65,426,162,90,342,284,374,204,464,9,280,391,491,231,298,284,82,417,355,356,207,367,262,244,283,489,477,143,495,472,372,447,322,399,239,450,168,202,89,333,276,199,416,490,494,488,137,327,113,189,430,320,197,120,71,262,31,295,218,74,238,169,489,308,300,260,397,308,328,267,419,84,357,486,289,312,230,64,468,227,268,28,243,267,254,153,407,399,346,385,77,297,273,484,366,482,491,368,221,423,107,272,98,309,426,181,320,77,185,382,478,398,476,22,328,450,299,211,285,62,344,484,395,466,291,487,301,407,28,295,36,429,99,462,240,124,261,387,30,362,161,156,184,188,99,377,392,442,300,98,285,312,312,365,415,367,105,81,378,413,43,326,490,320,266,390,53,327,75,332,454,29,370,392,360,1,335,355,344,120,417,455,93,60,256,451,188,161,388,338,238,26,275,340,109,185};
    cout<<s.wiggleMaxLength(in)<<endl;
    return 0;
}